package shapes.shapes2D.polygon 
{
	import flash.geom.Point;
	/**
	 * ...
	 * @author Nicolas Barradeau
	 * http://en.nicoptere.net
	 */
	public class ConvexHull
	{
		
		public function ConvexHull() { }
		
		//var points:Array = new Array();
		//stage.addEventListener(MouseEvent.CLICK, onClick);
		//stage.addEventListener(KeyboardEvent.KEY_UP, onKey);
		//function onClick(event:MouseEvent):void
		//{
		//var p:Point = new Point(mouseX,mouseY);
		//points.push(p);
		//graphics.clear();
		//drawPoints();
		//var hull:Array = convexHull(points);
		//drawHull(hull);
		//}
//
		//function onKey(event:KeyboardEvent):void
		//{
		//graphics.clear();
		//points = new Array();
		//}

		static public function process( original:Vector.<Point> ):Vector.<Point>
		{
			var points:Vector.<Point> = original.concat();
			points.sort( xSort );
			
			var angle:Number = Math.PI / 2;
			
			var point:Point = points[ 0 ];
			
			var hull:Array = [];
			
			
			while ( point != hull[ 0 ] )
			{
				
				hull.push( point );
				
				var bestAngle:Number = Number.MAX_VALUE;
				var bestIndex:int;
				
				for (var i:int = 0; i < points.length; i++)
				{
					
					var testPoint:Point = points[i] as Point;
					if (testPoint == point)
					{
						continue;
					}
					
					var dx:Number = testPoint.x - point.x;
					var dy:Number = testPoint.y - point.y;
					
					var testAngle:Number = Math.atan2(dy,dx);
					testAngle -= angle;
					while (testAngle < 0)
					{
						testAngle += Math.PI * 2;
					}
					
					if ( testAngle < bestAngle ) 
					{
						bestAngle = testAngle;
						bestIndex = i;
					}
					
				}
				point = points[bestIndex];
				angle += bestAngle;
				
			}
			
			return Vector.<Point>( hull );
		}
		
		static private function xSort( a:Point, b:Point):Number
		{
			return a.x < b.x ? -1 : 1;
		}

	}

}